/*
	解法：滑动窗口遍历s字符串 + 哈希表记录当前窗口中满足 need 需求的<字符, 出现次数>
	为什么这样想：求最短/最长连续区间，且区间内满足某个条件。
	时间复杂度：O(|S| + |T|)，空间复杂度：O(|Σ|)，Σ 是字符集（最多 52 个字母）
 */

#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>	//使用INT_MAX

using namespace std;

class Solution 
{
public:
	string minWindow(string s, string t) 
	{
		unordered_map<char, int> need;		//记录 t 中每个字符需要出现的次数
		unordered_map<char, int> window;	//记录当前窗口中满足 need 需求的<字符, 出现次数>
		
		for(int i = 0; i < (int)t.size(); i++)
		{
			char c = t[i];
			need[c]++;
		}
		
		int left = 0, right = 0;
		int valid = 0;  // 记录当前窗口中有多少个字符满足 need 需求，不含重复字符
		int start = 0;  // 最小覆盖子串的起始位置
		int len = INT_MAX;  // 最小覆盖子串的长度
		
		while (right < (int)s.size()) 
		{
			char c = s[right];
			right++;
			
			if (need.count(c)) 
			{
				window[c]++;
				if (window[c] == need[c]) 
				{
					valid++;
				}
			}
			
			while (valid == (int)need.size()) //尝试缩小窗口，找更短的子串
			{
				if (right - left < len) 
				{
					start = left;
					len = right - left;
				}
				
				char d = s[left];
				left++;
				
				if (need.count(d)) 
				{
					if (window[d] == need[d]) 
					{
						valid--;
					}
					window[d]--;
				}
			}
		}
		
		return len == INT_MAX ? "" : s.substr(start, len);
	}
};

int main() 
{
	Solution sol;
	string s, t;
	
	cout << "请输入字符串 s: ";
	cin >> s;
	cout << "请输入字符串 t: ";
	cin >> t;
	
	string result = sol.minWindow(s, t);
	cout << "最小覆盖子串: " << result << endl;
	
	return 0;
}


